\section{Vectorization (SSE)}
\label{sec:vectorization}

\subsection{Introduction}
\label{ssec:sse_introduction}

Vectorization is basically the way to process multiple blocks (contiguous and aligned) of same data type together. Vectorization is used to convert a program from a scalar implementation, which does an operation on a pair of operands at a time to a vector implementation, where the single operation or instruction can be performed on multiple or a series of adjacent operands together. This is specially effective when we perform some operation over multiple arrays of data. For example, We have two arrays of data $A$ and $B$, and we have a pointwise operation $*$ requiring the two arrays, and generating a third array $C$ such that $C[i] = A[i] * B[i]$ . In a naive loop implementation, the code to do this will look like something as follows:\\

\vspace{2mm}
for($i=0$; $i<Array\_Length$;$i++$)\{

	\hspace{5mm}Fetch $A[i]$;

	\hspace{5mm}Fetch $B[i]$;

	\hspace{5mm}Perform $A[i] * B[i]$;

	\hspace{5mm}Store Result in $C[i]$;

\}
\vspace{2mm}

Rather, We can bring $A[i], A[i+1], A[i+2], A[i+3]$ together, $B[i], B[i+1], B[i+2], B[i+3]$ together and load them in two 128 bit registers (asuming each variable of $A$ and $B$ array are of length 32 bit, which is normal for integer and single precision float), perform the $*$ operation on those tow registers, and store the result in consecutive four blocks of array $C$, viz. $C[i], C[i+1], C[i+2], C[i+3]$. This way we can make the code run much faster. Corresponding pseudocode is shown below:\\

\vspace{2mm}
for ($i=0$; $i<Array\_Length$;$i+=4$)
 \{

   \hspace{5mm}$vA = vec\_load(\&A[i])$;

   \hspace{5mm}$vB = vec\_load(\&B[i])$;

   \hspace{5mm}$vC = vec\_(*)(vA, vB)$;

   \hspace{5mm}$vec\_store(vC,\&C[i])$;

 \}
\vspace{2mm}

Here, $vec\_load$, $vec\_(*)$ and $vec\_store$ implies loading the vector of four integers to a register, performing $*$ blockwise on those register and storing the vector result respectively. The technique employed to achieve data level parallelism is called {\bf S}ingle {\bf I}nstruction {\bf M}ultiple {\bf D}ata or {\bf SIMD}. This is justified as we use multiple operand to produce multiple output data during a single instruction execution. SSE or {\bf S}treaming {\bf S}IMD {\bf E}xtensions is a SIMD instruction set extension to the x86 architecture. This one features eight 128-bit registers marked as XMM0 through XMM7. As shohwn in the example above, each register can hold four integer or single precision float type variables or two double precision float variables. During vectorization, the consecutive data blocks are actually aligned and loaded into one of these registers.\\


\subsection{Addition}
\label{ssec:sse_addition}

\subsection{Multiplication}
\label{ssec:sse_multiplication}
